﻿// Copyright (c) 2012, Alexander Endris
// All rights reserved.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions
// are met:
// * Redistributions of source code must retain the above copyright
//    notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright
//    notice, this list of conditions and the following disclaimer in the
//    documentation and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
// IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
// OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
// IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
// INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
// NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
// THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#region Usings

using NamelessOne.Imaging.IO;

#endregion

namespace NamelessOne.Imaging.Compression
{
  /// <summary>
  ///   Represents a huffman tree
  /// </summary>
  internal class HuffmanTree
  {
    #region Public / Attributes

    public byte Id
    {
      get { return id; }
    }

    public byte Type
    {
      get { return type; }
    }

    #endregion

    #region Public / Constructors

    public HuffmanTree(byte[] values, byte[] lengths, byte typeId)
    {
      this.values = values;
      type = (byte) (typeId >> 4 & 0xF);
      id = (byte) (typeId & 0xF);
      Initialize(lengths);
    }

    #endregion

    #region Public / Methods

    public int Decode(BitReader reader)
    {
      ushort code = (ushort) (reader.ReadBit() ? 1 : 0);
      int codeLength;

      for (codeLength = 0; (code > maxCode[codeLength] && codeLength < 16); codeLength++)
        code = (ushort) ((code << 1) | (reader.ReadBit() ? 1 : 0));

      int offset = code - minCode[codeLength];
      int index = valueIndices[codeLength] + offset;

      return values[index];
    }

    #endregion

    #region Private / Attributes

    private byte id;

    private int[] maxCode;
    private int[] minCode;
    private byte type;
    private byte[] valueIndices;
    private byte[] values;

    #endregion

    #region Private / Methods

    private void Initialize(byte[] lengths)
    {
      ushort[] codes = new ushort[256];
      uint[] sizes = new uint[257];

      for (int i = 0, k = 0; i < 16; i++)
      {
        for (int j = 0; j < lengths[i]; j++)
        {
          sizes[k] = (uint) (i + 1);
          k++;
        }
        sizes[k] = 0;
      }

      ushort code = 0;
      uint si = sizes[0];
      for (int i = 0; sizes[i] != 0; si++, code <<= 1)
      {
        while (sizes[i] == si)
        {
          codes[i] = code;
          code++;
          i++;
        }
      }

      maxCode = new int[16];
      minCode = new int[16];
      valueIndices = new byte[16];

      for (int i = 0, j = 0; i < 16; i++)
      {
        if (lengths[i] != 0)
        {
          valueIndices[i] = (byte) j;
          minCode[i] = codes[j];
          j += lengths[i];
          maxCode[i] = codes[j - 1];
        }
        else
        {
          maxCode[i] = -1;
          minCode[i] = 257;
          valueIndices[i] = 0;
        }
      }
    }

    #endregion
  }
}